/**
   链表：
    不需要-构造函数
 */
public class LinkedList<E> extends AbstractList<E> {
  private Node<E> firstNode;

  private static class Node<E> {
    E element;
    Node<E> next;

    public Node(E element, Node<E> next) {
      this.element = element;
      this.next = next;
    }
  }

  public void clear() {
    firstNode = null;
    size = 0;
  }

  @Override
  public void add (int index, E element) {
    if (index == 0) {
      firstNode = new Node<E>(element, firstNode);
    } else {
      Node<E> prev = node(index - 1);
      prev.next = new Node<E>(element, prev.next);
    }
    size ++;
  }

  @Override
  public E get(int index) {
    return node(index).element;
  }

  @Override
  public E set(int index, E element) {
    Node<E> node = node(index);
    E old = node.element;
    node.element = element;
    return old;
  }

  @Override
  public E remove(int index) {
    rangeCheck(index);
    Node<E> oldNode = firstNode;
    if (index == 0) {
      if (firstNode != null && firstNode.next != null) {
        firstNode.next = firstNode.next.next;
        size --;
      }
    } else {
      Node<E> prev = node(index - 1);
      oldNode = prev.next;
      prev.next = prev.next.next;
      size --;
    }
    return oldNode.element;
  }

  @Override
  public int indexOf(E element) {
    Node<E> node = firstNode;
    for (int i = 0; i < size; i++) {
      if (node.element == null) return i;
      node = node.next;
    }
    return ELEMENT_NOT_FOUND;
  }

  private Node<E> node(int index) {
    rangeCheck(index);
    Node<E> node = firstNode;
    for (int i = 0; i < index; i++) {
      node = node.next;
    }
    return node;
  }

  @Override
  public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [\n");

    Node<E> node = firstNode;

    for (int i = 0; i < size; i++) {
      if (i != 0) { // 1
        string.append(", \n");
      }
      string.append("  ");
      string.append(node.element);
      node = node.next;
    }

    string.append("\n]");
    return string.toString();
  }

}